Batch 3 - Class 195 - Parity II

• (Khan Academy) 10 prisoners are given a chance of survival by the jailer. The jailer tells them that the next morning, he will have them stand in a queue (so that the last person can see the nine people in front, the second last people can see eight people in front of him, and so on), and then place either a red hat or a purple hat on each person's head. The person hence will be able to see the color of hat for people in front of him (but not his own hat). The jailer will then start from the last person, and ask each person "What is the color of hat on your head". The person can answer "red" or "purple". If the person's answer is correct, he will be released, else he will be killed. The jailer will then ask the same question to the second last person, and so on. The prisoners have the night to figure out the strategy so that maximum number of prisoners can survive (on a guaranteed basis). Figure out a strategy to save the maximum number of prisoners.
• Answer: "Last guy calls the odd number of hats in front". Every person there on keeps a count of odd or even parity.

• Review principles of Parity
• Parity means "equal" or "at par" - typically involving separating the possibilities into two parts. Those two parts could be even or odd, black or white, clockwise or anticlockwise, and so on
• Thinking of a problem as a parity problem is often non-trivial. Sometimes looking at specific cases, or smaller problems and patterns helps.

• (MCDiaries 1 - Chap 7 - 2b) A hacker has programmed a 100- stories elevator so that only 2 buttons are working. The first takes the elevator 8 stories up, and the second one takes it 6 stories down. Starting at the first floor, can the elevator reach 96th floor?
• Answer: No, because the elevator will always remain on an odd floor
• (MCDiaries 1 - Chap 7 - 4) In a land far away, there lived 9 happy and 9 unhappy princesses. The magician has learned spells which can make two unhappy princesses happy, or two happy princesses unhappy, or switch the moods of a happy and unhappy princess. Can he use these three spells to make everyone happy?
• Answer: No. The number of happy or unhappy princesses can only change by an even number, and since the initial number of unhappy princesses is odd, one cant get to zero unhappy princesses
• To be incorporated: MC Diaries Y1, Chap 7 - Problem 5
• Game: - There is a circular table on which two people are playing a game of placing checkers. The person who can place the last checker wins. If you are the first player to go, how will you win?
• Answer: Place first move in center, then place every checker symmetrically opposite to what the opponent does. What if it is a hexagonal table?

• (MartinShCol - 1.16) In the class, you are allowed to shake hands with each other as many number of times as you want. At every stage, people who have shaken hands odd number of times remain standing. Tell your observation.
• Answer: Number of people standing is always even. Why?
• A loose leaf notebook contains 100 sheets of paper. Number them, front and back, from 1 to 200. Tear out any 25 of the sheets, and add up the 50 page numbers on them. Can you choose the sheets so that the total is 2010?
• Answer: No. The sum of numbers on each page is odd, and there are odd number of pages. So the total must be odd.
• There are two equally matched teams playing a best of 7 tournament. Is the tournament more likely to be decided on 6 games or 7?
• Answer: Equally likely. For the game to go to 6 or 7 games, the score at end of 5 games must be 3:2. Now if the first team wins the next game, its a 6-game finish, else 7. Given that the teams are equally matched, its equally likely.

• (MartinShCol - 1.6) Take a 3x3 Rubik cube. A termite starts at one of the outer cubes, and goes from one cube to next, never coming back to a cube it has been through, and never going diagonal. Is it possible for the termite to bore through each of 26 outer cubes and finish the trip at the center cube?
• Answer: No. Color alternate cubes black and white. Termite alternates between colors on the cube, and hence can not finish at the center square, which is in the 13 color set (not in the 14 color set)